package leetcode;

import java.util.*;

@SuppressWarnings({"all"})
// 动态规划
public class Demo7 {

    //746. 使用最小花费爬楼梯
    // 解法一：
    //public int minCostClimbingStairs(int[] cost) {
    //        int n = cost.length;
    //        int[] dp = new int[n + 1];
    //        dp[0] = dp[1] = 0;
    //        for(int i = 2; i <= n; i++) {
    //            dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
    //        }
    //        return dp[n];
    //    }

    // 解法二： dp[i] 表示从 i 位置开始到达 楼梯顶部的最小花费
    public int minCostClimbingStairs(int[] cost) {
        // 解法二： dp[i] 表示从 i 位置开始到达 楼梯顶部的最小花费
        int n = cost.length;
        int[] dp = new int[n];
        dp[n - 1] = cost[n - 1];
        dp[n - 2] = cost[n - 2];
        for (int i = n - 3; i >= 0; i--) {
            dp[i] = Math.min(dp[i + 1], dp[i + 2]) + cost[i];
        }

        return Math.min(dp[0], dp[1]);
    }


    //91. 解码方法
    public int numDecodings(String s) {
        // 状态表示: dp[i] 表示为 i 位置为结尾时，解码方法的总数
        // 若 i 位置单独解码时，解码成功 -> 有dp[i-1]种方法
        // 若 i 和 i-1 位置联合解码时，解码成功 -> 有dp[i-2]种方法
        // 因此 dp[i] = dp[i-1] + dp[i-2]


        // 1. 创建 dp 表
        int n = s.length();
        int[] dp = new int[n];
        char[] arr = s.toCharArray();
        // 2. 初始化 dp[0] 和 dp[1]
        if (arr[0] != '0') dp[0] = 1;
        if (n == 1) return dp[0];

        int a = arr[0] - '0', b = arr[1] - '0';     // a 前一个数字， b表示后面一个数字
        if (a >= 1 && a <= 9 && b >= 1 && b <= 9) dp[1]++;
        if (a * 10 + b >= 10 && a * 10 + b <= 26) dp[1]++;
        // 3. 进行填表
        for (int i = 2; i < n; i++) {
            a = arr[i - 1] - '0';
            b = arr[i] - '0';
            if (b >= 1 && b <= 9) dp[i] += dp[i - 1];
            if (a * 10 + b >= 10 && a * 10 + b <= 26) dp[i] += dp[i - 2];
        }
        // 4. 返回结果
        return dp[n - 1];
    }


    //62. 不同路径
    public int uniquePaths(int m, int n) {
        // 动态规划：dp[i][j]表示以 i，j位置为终点，共有多少种方式可以到达
        int[][] dp = new int[m + 1][n + 1];
        dp[1][0] = 1;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m][n];
    }


    //63. 不同路径 II
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // 1. 创建 dp 表， dp[i][j]表示到达 i,j位置有多少种方法
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        dp[0][1] = 1;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (obstacleGrid[i - 1][j - 1] == 1) dp[i][j] = 0;
                else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }


    //LCR 166. 珠宝的最高价值
    public int jewelleryValue(int[][] frame) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int m = frame.length, n = frame[0].length;
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
            }
        }

        return dp[m][n];
    }


    //931. 下降路径最小和
    public int minFallingPathSum(int[][] matrix) {

        // 1. 创建 dp 表
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m + 1][n + 2];
        // 2. 初始化:将 dp 表左右两列的值赋值为无穷大
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i][m + 1] = Integer.MAX_VALUE;
        }
        // 3. 填表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j + 1], Math.min(dp[i - 1][j - 1], dp[i - 1][j])) + matrix[i - 1][j - 1];
            }
        }
        // 4. 返回值
        int ret = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            ret = Math.min(ret, dp[m][i]);
        }
        return ret;
    }


    //64. 最小路径和
    public int minPathSum(int[][] grid) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m + 1][n + 1];

        for (int j = 1; j <= n; j++) dp[0][j] = Integer.MAX_VALUE;
        for (int i = 2; i <= m; i++) dp[i][0] = Integer.MAX_VALUE;

        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];

        return dp[m][n];
    }


    //174. 地下城游戏
    public int calculateMinimumHP(int[][] dungeon) {
        // 1. 创建 dp 表
        // 2. 初始化 : 从最下面一行和最右边一列开始初始化
        // 3. 填表
        // 4. 返回值
        int m = dungeon.length, n = dungeon[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) dp[i][n] = Integer.MAX_VALUE;
        for (int j = 0; j <= n; j++) dp[m][j] = Integer.MAX_VALUE;
        dp[m][n - 1] = dp[m - 1][n] = 1;

        for (int i = m - 1; i >= 0; i--)
            for (int j = n - 1; j >= 0; j--)
                dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);

        return dp[0][0];
    }




    //343. 整数拆分
    public int integerBreak(int n) {
        // dp[i]:以整数i为结尾，将其拆分成 若干个 正整数的乘积的最大值
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for(int i = 3; i <= n; i++) {
            for(int j = 1; j <= i - 1; j++) {
                dp[i] = Math.max(Math.max(j, dp[j]) * (i - j), dp[i]);
            }
        }
        return dp[n];
    }




    //42. 接雨水
    public int trap(int[] height) {
        // 按每一列求雨水的面积
        // 先用 dp 表保存每个位置 左边和右边最高柱子的高度，避免重复计算
        int n = height.length;
        int[] left_dp = new int[n], right_dp = new int[n];
        left_dp[0] = right_dp[n - 1] = 0;
        for(int i = 1; i < n; i++) left_dp[i] = Math.max(height[i - 1], left_dp[i - 1]);
        for(int i = n - 2; i >= 0; i--) right_dp[i] = Math.max(height[i + 1], right_dp[i + 1]);

        int ret = 0;
        for(int i = 1; i < n - 1; i++) {    // 第1列和最后一列不能接雨水,不用计算
            // max_left 和 max_right 中的较小值比 height[i] 大， 则更新结果
            int minHeight = Math.min(left_dp[i], right_dp[i]);
            if(minHeight > height[i]) ret += minHeight - height[i];
        }
        return ret;
    }



    //面试题 17.16. 按摩师
    public int massage(int[] nums) {
        // 1. 创建 dp 表： dp[i]表示以 i 位置为结尾，预约的时间最长
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int n = nums.length;
        if (n == 0) return 0;

        int[] f = new int[n], g = new int[n];
        f[0] = nums[0];

        for (int i = 1; i < n; i++) {
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }

        return Math.max(f[n - 1], g[n - 1]);
    }


    //198. 打家劫舍
    public int rob(int[] nums) {
        int n = nums.length;
        int[] f = new int[n], g = new int[n];
        f[0] = nums[0];

        for (int i = 1; i < n; i++) {
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }

        return Math.max(f[n - 1], g[n - 1]);
    }


    //213. 打家劫舍 II
    public int rob2(int[] nums) {
        int n = nums.length;
        return Math.max(rob2(nums, 2, n - 2) + nums[0], rob2(nums, 1, n - 1));
    }

    private int rob2(int[] nums, int x, int y) {
        if (x > y) return 0;

        int n = nums.length;
        int[] f = new int[n], g = new int[n];
        f[x] = nums[x];
        for (int i = x + 1; i <= y; i++) {
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        return Math.max(f[y], g[y]);
    }


    //740. 删除并获得点数
    public int deleteAndEarn(int[] _nums) {
        int n = _nums.length, max = 0;
        for (int x : _nums) max = Math.max(max, x);
        int[] nums = new int[max + 1];
        for (int x : _nums) nums[x] += x;

        // 创建 dp 表
        // 初始化
        // 填表
        // 确定返回值
        int[] f = new int[max + 1], g = new int[max + 1];
        f[1] = nums[1];
        for (int i = 2; i <= max; i++) {
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        return Math.max(f[max], g[max]);
    }


    //LCR 091. 粉刷房子
    public int minCost(int[][] costs) {
        int n = costs.length;
        int[][] dp = new int[n + 1][3];

        for (int i = 1; i <= n; i++) {
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];
        }

        return Math.min(dp[n][0], Math.min(dp[n][1], dp[n][2]));
    }


    //最佳买卖股票时机含冷冻期
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][3];
        dp[0][0] = -prices[0];

        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][0] + prices[i];
        }

        return Math.max(dp[n - 1][1], dp[n - 1][2]);
    }


    //714. 买卖股票的最佳时机含手续费
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = -prices[0];

        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }

        return dp[n - 1][1];
    }


    //122. 买卖股票的最佳时机 II
    public int maxProfit2(int[] prices) {
        int n = prices.length;
        int[] f = new int[n], g = new int[n];
        f[0] = -prices[0];

        for (int i = 1; i < n; i++) {
            f[i] = Math.max(f[i - 1], g[i - 1] - prices[i]);
            g[i] = Math.max(g[i - 1], f[i - 1] + prices[i]);
        }

        return g[n - 1];
    }


    //123. 买卖股票的最佳时机 III
    public int maxProfit3(int[] prices) {
        int n = prices.length;
        int[][] f = new int[n][3];
        int[][] g = new int[n][3];
        f[0][0] = -prices[0];
        f[0][1] = f[0][2] = g[0][1] = g[0][2] = -0X3f3f3f3f;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= 2; j++) {
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j >= 1) g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        }

        int ret = -0X3f3f3f3f;
        for (int j = 0; j <= 2; j++) {
            ret = Math.max(g[n - 1][j], ret);
        }
        return ret;
    }


    //188. 买卖股票的最佳时机 IV
    public int maxProfit(int k, int[] prices) {
        int min = -0X3f3f3f3f;
        int n = prices.length;
        int[][] f = new int[n][k + 1], g = new int[n][k + 1];
        f[0][0] = -prices[0];
        for (int j = 1; j <= k; j++) {
            f[0][j] = g[0][j] = min;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j >= 1) g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        }

        int ret = min;
        for (int j = 0; j <= k; j++) {
            ret = Math.max(ret, g[n - 1][j]);
        }
        return ret;
    }


    //53. 最大子数组和
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];

        int ret = dp[0];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            ret = Math.max(ret, dp[i]);
        }

        return ret;
    }


    //918. 环形子数组的最大和
    public int maxSubarraySumCircular(int[] nums) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int n = nums.length;
        int[] f = new int[n + 1], g = new int[n + 1];

        int sum = 0, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            sum += nums[i - 1];
            f[i] = Math.max(nums[i - 1], f[i - 1] + nums[i - 1]);
            g[i] = Math.min(nums[i - 1], g[i - 1] + nums[i - 1]);
            max = Math.max(max, f[i]);
            min = Math.min(min, g[i]);
        }

        if (sum == min) return max;
        return Math.max(max, sum - min);
    }


    //152. 乘积最大子数组
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] f = new int[n], g = new int[n];
        f[0] = g[0] = nums[0];

        int ret = f[0];
        for (int i = 1; i < n; i++) {
            int x = nums[i], y = f[i - 1] * nums[i], z = g[i - 1] * nums[i];
            f[i] = Math.max(x, Math.max(y, z));
            g[i] = Math.min(x, Math.min(y, z));
            ret = Math.max(ret, f[i]);
        }

        return ret;
    }


    //1567. 乘积为正数的最长子数组长度
    public int getMaxLen(int[] nums) {
        // f[i]: 以 i 位置为结尾的所有子数组中 乘积为正数的最长子数组的长度
        // g[i]: 以 i 位置为结尾的所有子数组中 乘积为负数的最长子数组的长度
        int n = nums.length;
        int[] f = new int[n + 1], g = new int[n + 1];

        int ret = f[0];
        for (int i = 1; i <= n; i++) {
            if (nums[i - 1] > 0) {
                f[i] = f[i - 1] + 1;
                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
            } else if (nums[i - 1] < 0) {
                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
                g[i] = f[i - 1] + 1;
            }
            ret = Math.max(ret, f[i]);
        }
        return ret;
    }


    //413. 等差数列划分
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        if (n == 1 || n == 2) return 0;

        int[] dp = new int[n];
        dp[0] = dp[1] = 0;

        int ret = 0;
        for (int i = 2; i < n; i++) {
            dp[i] = nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] ? dp[i - 1] + 1 : 0;
            ret += dp[i];
        }
        return ret;
    }


    //978. 最长湍流子数组
    public int maxTurbulenceSize(int[] arr) {
        // f[i]: 以 i 位置为结尾，且呈现“上升”状态的湍流子数组的最大长度
        // g[i]: 以 i 位置为结尾，且呈现“下降”状态的湍流子数组的最大长度

        int n = arr.length;
        int[] f = new int[n], g = new int[n];
        for (int i = 0; i < n; i++) f[i] = g[i] = 1;

        int ret = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i] - arr[i - 1] > 0) f[i] = g[i - 1] + 1;
            if (arr[i] - arr[i - 1] < 0) g[i] = f[i - 1] + 1;
            ret = Math.max(ret, Math.max(f[i], g[i]));
        }

        return ret;
    }


    //139. 单词拆分
    public boolean wordBreak(String s, List<String> wordDict) {
        // dp[i]: 以 i 位置为结尾的字符串能否被单词拼接而成
        // j 表示 0 ~ i 中最后一个单词的起始位置
        Set<String> hash = new HashSet<>(wordDict);

        s = " " + s;
        int n = s.length();
        boolean[] dp = new boolean[n];
        dp[0] = true;

        for (int i = 1; i < n; i++) {
            for (int j = i; j >= 1; j--) {
                if (dp[j - 1] && hash.contains(s.substring(j, i + 1))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n - 1];
    }



    //140. 单词拆分 II
    public List<String> wordBreak2(String s, List<String> wordDict) {
        Set<String> hash = new HashSet<>();     // 记录字典中出现的单词
        hash.addAll(wordDict);

        // dp[i]:若第 0 ~ i 个字母能够构成句子，增加单词间的空格，存放所有合法的句子
        int n = s.length();
        s = " " + s;
        List<List<String>> dp = new ArrayList<>();
        dp.add(new ArrayList<>());

        for (int i = 1; i <= n; i++) {
            dp.add(new ArrayList<>());

            for (int j = i; j >= 1; j--) {
                if ((j - 1 == 0 || dp.get(j - 1).size() > 0) && hash.contains(s.substring(j, i + 1))) {
                    String str = s.substring(j, i + 1);
                    List<String> cur = dp.get(i);
                    List<String> list = dp.get(j - 1);

                    // 在之前的句子后面拼接 当前的单词
                    for(int k = 0; k < list.size(); k++) {
                        StringBuffer tmp = new StringBuffer(list.get(k));
                        tmp.append(" ");
                        tmp.append(str);
                        cur.add(tmp.toString());
                    }
                    // 前面的句子若为空，直接添加该单词
                    if(j - 1 == 0) {
                        cur.add(str);
                    }

                }
            }
        }
        return dp.get(n);
    }


    //467. 环绕字符串中唯一的子字符串
    public int findSubstringInWraproundString(String ss) {
        // dp[i]: 以 i 位置的元素为结尾的所有子串中，有多少个在 base中出现过
        // hash[i]: 表示以 a ~ z 位置为结尾的最长子串的 dp值；避免重复计算
        int n = ss.length();
        char[] s = ss.toCharArray();
        int[] dp = new int[n], hash = new int[26];
        for (int i = 0; i < n; i++) dp[i] = 1;
        hash[s[0] - 'a']++;

        for (int i = 1; i < n; i++) {
            if (s[i] - 1 == s[i - 1] || s[i - 1] == 'z' && s[i] == 'a')
                dp[i] += dp[i - 1];
            hash[s[i] - 'a'] = Math.max(hash[s[i] - 'a'], dp[i]);
        }
        int ret = 0;
        for (int x : hash) ret += x;
        return ret;
    }


    //300. 最长递增子序列
    public int lengthOfLIS(int[] nums) {
        // dp[i]: 以 i 位置元素为结尾的所有递增子序列中最长递增子序列的长度
        int n = nums.length;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) dp[i] = 1;

        int ret = 1;
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }


    //376. 摆动序列
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        int[] f = new int[n], g = new int[n];
        for (int i = 0; i < n; i++) f[i] = g[i] = 1;

        int ret = 1;
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] < nums[i]) f[i] = Math.max(f[i], g[j] + 1);
                if (nums[j] > nums[i]) g[i] = Math.max(g[i], f[j] + 1);
            }
            ret = Math.max(ret, Math.max(f[i], g[i]));
        }
        return ret;
    }


    //673. 最长递增子序列的个数
    public int findNumberOfLIS(int[] nums) {
        // len[i]: 以 i 位置为结尾的所有子序列的最长子序列的长度
        // count[i]: 以 i 位置为结尾的所有子序列的最长子序列的个数
        int n = nums.length;
        int[] len = new int[n], count = new int[n];
        for (int i = 0; i < n; i++) len[i] = count[i] = 1;

        int ret = 1;
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] < nums[i]) {
                    if (len[j] + 1 == len[i]) count[i] += count[j];
                    else if (len[j] + 1 > len[i]) {
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }
                }
            }
        }
        int maxLen = len[0], countLen = count[0];
        for (int i = 1; i < n; i++) {
            if (len[i] == maxLen) countLen += count[i];
            else if (len[i] > maxLen) {
                maxLen = len[i];
                countLen = count[i];
            }
        }
        return countLen;
    }


    //646. 最长数对链
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (o1, o2) -> o1[0] - o2[0]);

        int n = pairs.length;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) dp[i] = 1;

        int ret = 1;
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (pairs[j][1] < pairs[i][0]) {
                    dp[i] = dp[j] + 1;
                    break;
                }
            }
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }


    //1218. 最长定差子序列
    public int longestSubsequence(int[] arr, int difference) {
        // dp[i]: 以 i 位置元素为结尾的所有子序列，且元素之差为 difference 的最长子序列的长度

        int n = arr.length;
        Map<Integer, Integer> hash = new HashMap<>();   //key存储元素值，value存储对应dp[i]值

        int ret = 1;
        for (int x : arr) {
            hash.put(x, hash.getOrDefault(x - difference, 0) + 1);
            ret = Math.max(ret, hash.get(x));
        }
        return ret;
    }


    //LCR 093. 最长的斐波那契子序列的长度
    public int lenLongestFibSubseq(int[] arr) {
        // dp[i][j]: i < j, 以 i、j位置分别为倒数第二 和 倒数第一个元素的所有斐波那契子序列的最大长度
        int n = arr.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = i; j < n; j++)
                dp[i][j] = 2;
        Map<Integer, Integer> hash = new HashMap<>();   // 元素 及 下标值
        for (int i = 0; i < n; i++) hash.put(arr[i], i);

        int ret = 2;
        for (int j = 2; j < n; j++) {            // 固定倒数第一个数
            for (int i = j - 1; i >= 1; i--) {   // 固定倒数第二个数
                int k = arr[j] - arr[i];
                if (hash.containsKey(k) && k < arr[i]) dp[i][j] = dp[hash.get(k)][i] + 1;
                ret = Math.max(ret, dp[i][j]);
            }
        }
        return ret < 3 ? 0 : ret;
    }


    //1027. 最长等差数列
    public int longestArithSeqLength(int[] nums) {
        // dp[i][j]: i < j,  以 i和j位置为结尾的所有子序列中，最长等差子序列的长度
        int n = nums.length;
        int[][] dp = new int[n][n];
        for (int[] arr : dp)
            Arrays.fill(arr, 2);

        int ret = 2;
        Map<Integer, Integer> hash = new HashMap<>();
        hash.put(nums[0], 0);
        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int x = nums[j] - nums[i];
                if (hash.containsKey(nums[i] - x)) {
                    dp[i][j] = dp[hash.get(nums[i] - x)][i] + 1;
                    ret = Math.max(ret, dp[i][j]);
                }
            }
            hash.put(nums[i], i);
        }
        return ret;
    }


    //446. 等差数列划分 II - 子序列
    public int numberOfArithmeticSlices2(int[] nums) {
        // dp[i][j]: i < j, 以 i和j 为结尾的所有等差序列的个数
        int n = nums.length;
        if (n < 3) return 0;
        Map<Integer, List<Integer>> hash = new HashMap<>(); // 记录所有相同元素 及 元素所在下标
        hash.put(nums[0], new ArrayList<>());
        hash.get(nums[0]).add(0);
        int[][] dp = new int[n][n];

        int ret = 0;
        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long num = (2 * (long) nums[i] - nums[j]);
                if (num < Integer.MIN_VALUE || num > Integer.MAX_VALUE) continue;
                int k = (int) num;
                if (hash.containsKey(k)) {
                    for (int x : hash.get(k)) {
                        dp[i][j] += dp[x][i] + 1;
                    }
                    ret += dp[i][j];
                }
            }
            if (!hash.containsKey(nums[i]))
                hash.put(nums[i], new ArrayList<>());
            hash.get(nums[i]).add(i);
        }
        return ret;
    }


    //647. 回文子串
    public int countSubstrings(String ss) {
        // dp[i][j]: 下标 i ~ j 位置的字符串能否构成一个回文字符串
        int n = ss.length();
        char[] s = ss.toCharArray();
        boolean[][] dp = new boolean[n][n];

        int ret = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= i; j--) {
                if (i == j) dp[i][j] = true;
                else if (i + 1 == j && s[i] == s[j]) dp[i][j] = true;
                else if (i < j && s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1];
                if (dp[i][j]) ret++;
            }
        }
        return ret;
    }


    //5. 最长回文子串
    public String longestPalindrome(String ss) {
        char[] s = ss.toCharArray();
        int n = s.length;
        boolean[][] dp = new boolean[n][n];

        int begin = 0, len = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= i; j--) {
                if (s[i] == s[j]) dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                if (dp[i][j] && j - i + 1 > len) {
                    begin = i;
                    len = j - i + 1;
                }
            }
        }
        return ss.substring(begin, begin + len);
    }


    //1745. 分割回文串 IV
    public boolean checkPartitioning(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
            }
        }

        // 0 <= i < j <= n - 1    [0, i], (i + 1, j - 1), [j, n - 1]
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (dp[0][i] && dp[i + 1][j - 1] && dp[j][n - 1]) return true;
            }
        }
        return false;
    }


    //132. 分割回文串 II
    public int minCut(String s) {
        // dp[i][j] : 下标为 i 到 j 的字符串是否为回文子串
        // count[i] : 0 ~ i 位置的 所有子串 分割成回文子串所需的最小次数
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= i; j--) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                }
            }
        }

        int[] count = new int[n];
        for (int i = 0; i < n; i++) count[i] = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (dp[0][i]) count[i] = 0;
            else {
                for (int j = 1; j <= i; j++) {
                    if (dp[j][i]) count[i] = Math.min(count[j - 1] + 1, count[i]);
                }
            }
        }
        return count[n - 1];
    }


    //516. 最长回文子序列
    public int longestPalindromeSubseq(String s) {
        // dp[i][j]: 在区间i ~ j 的所有子序列中 最长回文子序列的长度
        int n = s.length();
        int[][] dp = new int[n][n];

        for (int i = n - 1; i >= 0; i--) {   // 从下往上，从左往右
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }


    //1312. 让字符串成为回文串的最少插入次数
    public int minInsertions(String s) {
        // dp[i][j]: 在区间 i ~ j 插入字符，使之成为回文串的最小插入次数
        int n = s.length();
        int[][] dp = new int[n][n];

        for (int i = n - 1; i >= 0; i--) {       // 从下往上，从左往右
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i + 1 < j) dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i][j - 1], dp[i + 1][j]) + 1;
                }
            }
        }
        return dp[0][n - 1];
    }


    //1143. 最长公共子序列
    public int longestCommonSubsequence(String text1, String text2) {
        // 选取第一个字符串 0 ~ i 区间以及 第二个字符串 0 ~ j 区间作为研究对象
        // dp[i][j]: 第一个字符串 0 ~ i 区间以及 第二个字符串 0 ~ j 区间所有子序列中 最长公共子序列的长度
        int m = text1.length(), n = text2.length();
        text1 = " " + text1;
        text2 = " " + text2;
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {       // 从上往下，从左往右
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i) == text2.charAt(j)) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }


    //1035. 不相交的线
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        // 选取第一个数组 0 ~ i 区间以及 第二个数组 0 ~ j 区间作为研究对象
        // dp[i][j]: 第一个数组 0 ~ i 区间以及 第二个数组 0 ~ j 区间所有子序列中 最长公共子序列的长度
        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }


    //115. 不同的子序列
    public int numDistinct(String s, String t) {
        // 选取 0 ~ i 区间代表字符串 s 的一个子串； 0 ~ j 区间代表字符串 t 的所有子序列
        // dp[i][j]: 在字符串 t区间 0 ~ j内的所有子序列中 包含 字符串 s 0 ~ i 区间这个子串的个数
        int m = t.length(), n = s.length();
        s = " " + s;
        t = " " + t;
        int[][] dp = new int[m + 1][n + 1];
        for (int j = 0; j <= n; j++) dp[0][j] = 1;

        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i][j - 1];
                if (t.charAt(i) == s.charAt(j)) dp[i][j] += dp[i - 1][j - 1];
            }
        return dp[m][n] % (int) (Math.pow(10, 9) + 7);

    }


    //44. 通配符匹配
    public boolean isMatch(String s, String p) {
        // dp[i][j]: 在字符串p 0 ~ j 区间的子串能否匹配 字符串s的 0 ~ i区间的子串
        int m = s.length(), n = p.length();
        s = " " + s;
        p = " " + p;
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int j = 1; j <= n; j++)
            if (p.charAt(j) == '*') dp[0][j] = true;
            else break;

        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (p.charAt(j) != '*') {
                    if (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i)) dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                }
        return dp[m][n];
    }


    //10. 正则表达式匹配
    public boolean isMatch2(String ss, String pp) {
        // dp[i][j]: 在字符串p 0 ~ j 区间的子串能否匹配 字符串s的 0 ~ i区间的子串
        int m = ss.length(), n = pp.length();
        ss = " " + ss;
        pp = " " + pp;
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int j = 2; j <= n; j += 2) {
            if (p[j] == '*') dp[0][j] = true;
            else break;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j] == '*') dp[i][j] = dp[i][j - 2] || (p[j - 1] == '.' || p[j - 1] == s[i]) && dp[i - 1][j];
                else dp[i][j] = (p[j] == '.' || p[j] == s[i]) && dp[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }


    //97. 交错字符串
    public boolean isInterleave(String ss1, String ss2, String ss3) {
        // dp[i][j]: s1中 1 ~ i 位置的字符串 和 s2中 1 ~ j 位置的字符串能否拼接成 s3中 1 ~ i+j 的字符串
        int m = ss1.length(), n = ss2.length();
        if (m + n != ss3.length()) return false;
        ss1 = " " + ss1;
        ss2 = " " + ss2;
        ss3 = " " + ss3;
        char[] s1 = ss1.toCharArray();
        char[] s2 = ss2.toCharArray();
        char[] s3 = ss3.toCharArray();
        boolean[][] dp = new boolean[m + 1][n + 1];

        dp[0][0] = true;                        // 初始化第一个位置
        for (int i = 1; i <= m; i++)             // 初始化第一列
            if (s1[i] == s3[i]) dp[i][0] = true;
            else break;
        for (int j = 1; j <= n; j++)             // 初始化第一行
            if (s2[j] == s3[j]) dp[0][j] = true;
            else break;

        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = s1[i] == s3[i + j] && dp[i - 1][j]       // 两种情况有一种成立即可，不可使用if， else if
                        || s2[j] == s3[i + j] && dp[i][j - 1];

        return dp[m][n];
    }


    //712. 两个字符串的最小ASCII删除和
    public int minimumDeleteSum(String ss1, String ss2) {
        // d[i][j]:s1中 0 ~ i 区间 和 s2中 0 ~ j 区间所有子序列中，公共子序列ASCII码值之和的最大值
        int m = ss1.length(), n = ss2.length();
        ss1 = " " + ss1;
        ss2 = " " + ss2;
        char[] s1 = ss1.toCharArray();
        char[] s2 = ss2.toCharArray();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + s1[i];
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

        int sum = 0;
        for (char ch : s1) if (ch != ' ') sum += ch;
        for (char ch : s2) if (ch != ' ') sum += ch;
        return sum - 2 * dp[m][n];

    }



    //72. 编辑距离
    public int minDistance(String word1, String word2) {
        // dp[i][j]: 使word1 0 ~ i 区间的子串 转换成 word2 0 ~ j 区间的子串 所使用的最小操作数
        int m = word1.length(), n = word2.length();
        word1 = " " + word1; word2 = " " + word2;

        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1; i <= m; i++) dp[i][0] = i;   // 初始化
        for(int j = 1; j <= n; j++) dp[0][j] = j;

        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(word1.charAt(i) == word2.charAt(j)) dp[i][j] = dp[i - 1][j - 1];
                else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
                }
            }
        }

        return dp[m][n];
    }



    //718. 最长重复子数组
    public int findLength(int[] nums1, int[] nums2) {
        // dp[i][j]:nums1中以 i 位置为结尾 和 nums2中以 j 位置为结尾的的所有子数组中最长重复子数组的长度
        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];

        int ret = 0;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    ret = Math.max(ret, dp[i][j]);
                }

        return ret;
    }


    //DP41 【模板】01背包
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), V = in.nextInt();     // 物品数量 , 最大体积
        int[] v = new int[n + 1];    // 体积和价值
        int[] w = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }

        // 第一个问题
        // dp[i][j]:前 i 个物品中，背包装取容量不超过 j 的所有情况的最大价值
        int[] dp = new int[V + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = V; j >= v[i]; j--) {      // 从右往左填表
                dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[V]);

        // 第二个问题
        // dp2[i][j]:前 i 个物品中，背包装取容量为 j 的所有情况的最大价值
        dp[0] = 0;
        for (int j = 1; j <= V; j++) dp[j] = -1;     // 表示该情况选不出来
        for (int i = 1; i <= n; i++) {
            for (int j = V; j >= v[i]; j--) {
                if (dp[j - v[i]] != -1)
                    dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[V] == -1 ? 0 : dp[V]);
    }


    //416. 分割等和子集
    public boolean canPartition(int[] nums) {
        int sum = 0, n = nums.length;
        for (int x : nums) sum += x;
        if (sum % 2 == 1) return false;
        sum /= 2;

        // dp[i][j]: 在前 i 个数中，能否凑出和为 j 的情况
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;

        for (int i = 1; i <= n; i++)
            for (int j = sum; j >= nums[i - 1]; j--) {
                dp[j] = dp[j] || dp[j - nums[i - 1]];
            }
        return dp[sum];
    }


    //LCR 102. 目标和
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0, n = nums.length;
        for (int x : nums) sum += x;
        if ((sum + target) % 2 == 1) return 0;
        int aim = (sum + target) / 2;

        int[] dp = new int[aim + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = aim; j >= nums[i - 1]; j--) {
                dp[j] += dp[j - nums[i - 1]];
            }
        return dp[aim];
    }


    //1049. 最后一块石头的重量 II
    public int lastStoneWeightII(int[] stones) {
        int sum = 0, n = stones.length;
        for (int x : stones) sum += x;
        int aim = sum / 2;

        int[] dp = new int[aim + 1];

        for (int i = 1; i <= n; i++)
            for (int j = aim; j >= stones[i - 1]; j--)
                dp[j] = Math.max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);

        return sum - 2 * dp[aim];
    }


    //DP42 【模板】完全背包
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), V = in.nextInt();
        int[] v = new int[n + 1], w = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }

        // dp[i][j]: 在前 i 个物品中，物品体积不超过 j 的所有选法中，能装取的最大价值
        int[][] dp = new int[n + 1][V + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= V; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - v[i] >= 0) dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i]] + w[i]);
            }
        System.out.println(dp[n][V]);

        // dp[i][j]: 在前 i 个物品中，物品体积等于 j 的所有选法中，能装取的最大价值
        dp = new int[n + 1][V + 1];
        for (int i = 1; i <= V; i++) dp[0][i] = -1;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= V; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - v[i] >= 0 &&
                        dp[i][j - v[i]] != -1) dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i]] + w[i]);
            }
        if (dp[n][V] == -1) System.out.println(0);
        else System.out.println(dp[n][V]);
    }


    //322. 零钱兑换
    public int coinChange(int[] coins, int amount) {
        // dp[i][j]: 从前 i 种硬币种，凑成总金额正好为 j 所需的最小硬币数
        int[] dp = new int[amount + 1];
        int maxValue = 0X3f3f3f3f, n = coins.length;
        for (int j = 1; j <= amount; j++) dp[j] = maxValue;

        for (int i = 1; i <= n; i++) {
            for (int j = coins[i - 1]; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);
            }
        }
        if (dp[amount] >= maxValue) return -1;
        return dp[amount];
    }


    //518. 零钱兑换 II
    public int change(int amount, int[] coins) {
        // dp[i][j]: 从前 i 种硬币种，凑成总金额正好为 j 的硬币组合数
        int n = coins.length;
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int i = 1; i <= n; i++)
            for (int j = coins[i - 1]; j <= amount; j++) {
                dp[j] += dp[j - coins[i - 1]];
            }
        return dp[amount];
    }


    //279. 完全平方数
    public int numSquares(int n) {
        // dp[i][j]: 前 i 个数中，数的平方和 正好凑成 j 所需数的最小个数
        int count = (int) Math.sqrt(n), INF = 0X3f3f3f3f;
        int[] dp = new int[n + 1];
        for (int j = 1; j <= n; j++) dp[j] = INF;

        for (int i = 1; i <= count; i++)
            for (int j = i * i; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        return dp[n];
    }


    //474. 一和零
    public int findMaxForm(String[] strs, int m, int n) {
        // dp[i][j][k]: 从前 i 个字符串中，挑选某些字符串，使 字符'0'的个数不超j，字符'1'的个数不超过k，子集的最大长度
        int len = strs.length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= len; i++) {
            int a = 0, b = 0;
            for (char ch : strs[i - 1].toCharArray())
                if (ch == '0') a++;
                else b++;

            for (int j = m; j >= a; j--)
                for (int k = n; k >= b; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - a][k - b] + 1);
                }
        }
        return dp[m][n];
    }


    //879. 盈利计划
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        // dp[i][j][k]: 在前 i 种工作中，工作人数不超过 j， 所选的工作子集的盈利至少为 k 的工作子集的总数
        int count = group.length;
        int[][] dp = new int[n + 1][minProfit + 1];
        for (int j = 0; j <= n; j++) dp[j][0] = 1;

        for (int i = 1; i <= count; i++) {
            for (int j = n; j >= group[i - 1]; j--) {
                for (int k = minProfit; k >= 0; k--) {
                    dp[j][k] += dp[j - group[i - 1]][Math.max(0, k - profit[i - 1])];
                    dp[j][k] %= 1000000007;
                }
            }
        }
        return dp[n][minProfit];
    }


    //LCR 104. 组合总和 Ⅳ
    public int combinationSum4(int[] nums, int target) {
        // dp[i]: 凑成总和为 i ，一共有多少种排列数
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i - nums[j] >= 0) dp[i] += dp[i - nums[j]];
            }
        }
        return dp[target];
    }



    //96. 不同的二叉搜索树
    public int numTrees(int n) {
        // dp[i]:从 1 ~ i 个结点中，所有互不相同的二叉搜索树的总数
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;

        for(int i = 2; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                // j 为根结点值，就 j- 1 为左子树结点数目，i - j 为右子树结点数目
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }


    // 1262. 可被三整除的最大和
    public int maxSumDivThree(int[] nums) {
        int n = nums.length;
        // dp[i][j]: 从前 i 个数中选取若干个数,使得其总和 sum % 3 == j 的最大和
        int[][] dp = new int[n + 1][3];
        for (int j = 1; j < 3; j++) dp[0][j] = -0X3f3f3f3f;

        for (int i = 1; i <= n; i++) {
            int modNum = nums[i - 1] % 3;
            for (int j = 0; j < 3; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][(j - modNum + 3) % 3] + nums[i - 1]);
            }
        }
        return dp[n][0];
    }
}
